home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-04 / gs24src.zip / IDICT.C < prev    next >
C/C++ Source or Header  |  1992-03-18  |  18KB  |  552 lines
  1. /* Copyright (C) 1989, 1992 Aladdin Enterprises.  All rights reserved.
  2.    Distributed by Free Software Foundation, Inc.
  3.  
  4. This file is part of Ghostscript.
  5.  
  6. Ghostscript is distributed in the hope that it will be useful, but
  7. WITHOUT ANY WARRANTY.  No author or distributor accepts responsibility
  8. to anyone for the consequences of using it or for whether it serves any
  9. particular purpose or works at all, unless he says so in writing.  Refer
  10. to the Ghostscript General Public License for full details.
  11.  
  12. Everyone is granted permission to copy, modify and redistribute
  13. Ghostscript, but only under the conditions described in the Ghostscript
  14. General Public License.  A copy of this license is supposed to have been
  15. given to you along with Ghostscript so you can know your rights and
  16. responsibilities.  It should be in a file named COPYING.  Among other
  17. things, the copyright notice and this notice must be preserved on all
  18. copies.  */
  19.  
  20. /* idict.c */
  21. /* Dictionaries for Ghostscript */
  22. #include "ghost.h"
  23. #include "alloc.h"
  24. #include "errors.h"
  25. #include "name.h"
  26. #include "packed.h"
  27. #include "save.h"            /* for value cache in names */
  28. #include "store.h"
  29. #include "iutil.h"            /* for obj_eq */
  30. #include "dict.h"            /* interface definition */
  31.  
  32. /*
  33.  * A dictionary is a structure of three elements (refs):
  34.  *
  35.  *    count - a t_integer whose value says how many entries
  36.  *    are occupied (N).
  37.  *
  38.  *    keys - a t_shortarray or t_array of N+1 elements, containing
  39.  *    the keys.
  40.  *
  41.  *    values - a t_array of N+1 elements, containing the values.
  42.  *
  43.  * In the packed form, unused or deleted entries contain packed_key_empty
  44.  * or packed_key_deleted respectively; in the unpacked form, unused
  45.  * or deleted entries contain a literal or executable null respectively.
  46.  * The first entry is always marked as a deleted entry, to avoid a
  47.  * special wrap-around check.
  48.  *
  49.  * Note that if the keys slot in the dictionary is new,
  50.  * all the key slots are new (more recent than the last save).
  51.  * We use this fact to avoid saving stores into packed keys
  52.  * for newly created dictionaries.
  53.  */
  54. #define dict_is_packed(dct) r_has_type(&(dct)->keys, t_shortarray)
  55. #define packed_key_empty (pt_tag(pt_integer) + 0)
  56. #define packed_key_deleted (pt_tag(pt_integer) + 1)
  57. #define packed_key_impossible pt_tag(pt_full_ref)    /* never matches */
  58. #define packed_name_key(nidx)\
  59.   ((nidx) <= packed_max_name_index ? pt_tag(pt_literal_name) + (nidx) :\
  60.    packed_key_impossible)
  61. /*
  62.  * Using a special mark for deleted entries causes lookup time to degrade
  63.  * as entries are inserted and deleted.  This is not a problem, because
  64.  * entries are almost never deleted.
  65.  */
  66. #define nslots(dct) r_size(&(dct)->values)
  67. #define npairs(dct) (nslots(dct) - 1)
  68.  
  69. /* Define the size of the largest valid dictionary. */
  70. /* This is limited by the size field of the keys and values refs, */
  71. /* and by the enumeration interface, which requires the size to */
  72. /* fit in an int. */
  73. const uint dict_max_size = max_ushort / 2 - 2;
  74.  
  75. /* Define the hashing function for names. */
  76. #define dict_name_index_hash(nidx) ((nidx) * 30503)
  77.  
  78. /* Define whether dictionaries are packed by default. */
  79. #define default_pack 1
  80.  
  81. /* Forward references */
  82. private int dict_create_contents(P3(uint size, dict *pdict, int pack));
  83.  
  84. /* Create a dictionary. */
  85. int
  86. dict_create(uint size, ref *pref)
  87. {    dict *pdict =
  88.       (dict *)alloc_refs(sizeof(dict) / sizeof(ref), "dict_create");
  89.     int code;
  90.     if ( pdict == 0 ) return e_VMerror;
  91.     code = dict_create_contents(size, pdict, default_pack);
  92.     if ( code < 0 ) return code;
  93.     make_tav_new(pref, t_dictionary, a_all, pdict, pdict);
  94.     return 0;
  95. }
  96. private int
  97. dict_create_unpacked_keys(uint asize, dict *pdict)
  98. {    ref *kp = alloc_refs(asize, "dict_create(keys)");
  99.     ref *zp;
  100.     register uint i;
  101.     if ( kp == 0 ) return e_VMerror;
  102.     make_tasv_new(&pdict->keys, t_array, a_all, asize,
  103.               refs, kp);
  104.     for ( zp = kp, i = asize; i; zp++, i-- )
  105.         make_null_new(zp);
  106.     r_set_attrs(kp, a_executable);    /* wraparound entry */
  107.     return 0;
  108. }
  109. private int
  110. dict_create_contents(uint size, dict *pdict, int pack)
  111. {    uint asize = (size == 0 ? 1 : size) + 1;
  112.     ref *vp = alloc_refs(asize, "dict_create(values)");
  113.     register uint i;
  114.     ref *zp;
  115.     if ( vp == 0 ) return e_VMerror;
  116.     make_tasv_new(&pdict->values, t_array, a_all, asize, refs, vp);
  117.     for ( zp = vp, i = asize; i; zp++, i-- )
  118.         make_null_new(zp);
  119.     if ( pack )
  120.        {    uint ksize = (asize + packed_per_ref - 1) / packed_per_ref;
  121.         ref_packed *pkp = (ref_packed *)alloc_refs(ksize, "dict_create(packed keys)");
  122.         ref_packed *pzp;
  123.         make_tasv_new(&pdict->keys, t_shortarray, a_all, asize,
  124.                   packed, pkp);
  125.         for ( pzp = pkp, i = 0; i < asize || i % packed_per_ref; pzp++, i++ )
  126.             *pzp = packed_key_empty;
  127.         *pkp = packed_key_deleted;    /* wraparound entry */
  128.        }
  129.     else                /* not packed */
  130.        {    int code = dict_create_unpacked_keys(asize, pdict);
  131.         if ( code < 0 ) return code;
  132.        }
  133.     make_tv_new(&pdict->count, t_integer, intval, 0);
  134.     return 0;
  135. }
  136.  
  137. /*
  138.  * Define a macro for searching a packed dictionary.  Free variables:
  139.  *    ref_packed kpack - holds the packed key.
  140.  *    uint hash - holds the hash of the name.
  141.  *    dict *pdict - points to the dictionary.
  142.  *    uint size - holds npairs(pdict).
  143.  *    int wrap - counts wraparounds, initialized to 0.
  144.  * Note that the macro is *not* enclosed in {}, so that we can access
  145.  * the values of kbot and kp after leaving the loop.
  146.  */
  147. #define packed_search(del,pre,post)\
  148.    int wrap = 0;\
  149.    ref_packed *kbot = pdict->keys.value.packed;\
  150.    register ref_packed *kp;\
  151.    for ( kp = kbot + (hash % size) + 2; ; )\
  152.     { if ( *--kp == kpack )\
  153.        { pre (pdict->values.value.refs + (kp - kbot));\
  154.      post;\
  155.        }\
  156.       else if ( !packed_ref_is_name(kp) )\
  157.        { /* Empty, deleted, or wraparound. Figure out which. */\
  158.      if ( *kp == packed_key_empty ) break;\
  159.      if ( kp == kbot )    /* wrap */\
  160.       { if ( wrap++ ) break;    /* 2 wraps */\
  161.         kp += size + 1;\
  162.       }\
  163.      else { del; }\
  164.        }\
  165.     }
  166.  
  167. /*
  168.  * Look up in a stack of dictionaries.  Store a pointer to the value slot
  169.  * where found, or to the (value) slot for inserting.
  170.  * Return 1 if found, 0 if not and there is room for a new entry in
  171.  * the top dictionary on the stack, or e_dictfull if the top dictionary
  172.  * is full and the key is missing.
  173.  * Note that pdbot <= pdtop, and the search starts at pdtop.
  174.  */
  175. int
  176. dict_lookup(const ref *pdbot, const ref *pdtop, const ref *pkey,
  177.   ref **ppvalue /* result is stored here */)
  178. {    const ref *pdref = pdtop;
  179.     name *kpname;
  180.     uint nidx;
  181.     ref_packed kpack;
  182.     uint hash;
  183.     int ktype;
  184.     int full = 1;            /* gets set to 0 or e_dictfull */
  185.     /* Compute hash.  The only types we bother with are strings, */
  186.     /* names, and (unlikely, but worth checking for) integers. */
  187.     switch ( r_type(pkey) )
  188.        {
  189.     case t_name:
  190.         kpname = pkey->value.pname;
  191. nh:        nidx = kpname->index;
  192.         hash = dict_name_index_hash(nidx);
  193.         kpack = packed_name_key(nidx);
  194.         ktype = t_name;
  195.         break;
  196.     case t_string:            /* convert to a name first */
  197.        {    ref nref;
  198.         int code = name_ref(pkey->value.bytes,
  199.                     r_size(pkey), &nref, 1);
  200.         if ( code < 0 ) return code;
  201.         kpname = nref.value.pname;
  202.        }    goto nh;
  203.     case t_integer:
  204.         hash = (uint)pkey->value.intval * 30503;
  205.         kpack = packed_key_impossible;
  206.         ktype = -1;
  207.         break;
  208.     default:
  209.         hash = r_btype(pkey) * 99;    /* yech */
  210.         kpack = packed_key_impossible;
  211.         ktype = -1;
  212.        }
  213.     do
  214.        {    dict *pdict = pdref->value.pdict;
  215.         uint size = npairs(pdict);
  216.         int wrap = 0;
  217.         register int etype;
  218.         /* Search the dictionary */
  219.         if ( dict_is_packed(pdict) )
  220.            {    ref_packed *pslot = 0;
  221.             packed_search(if ( pslot == 0 ) pslot = kp,
  222.                       *ppvalue =, return 1);
  223.             if ( full > 0 )    /* first dictionary */
  224.                {    if ( pslot == 0 )
  225.                  { if ( wrap == 2 )
  226.                      full = e_dictfull;
  227.                    else
  228.                      *ppvalue = pdict->values.value.refs +
  229.                        (kp - kbot),
  230.                      full = 0;
  231.                  }
  232.                 else
  233.                   *ppvalue = pdict->values.value.refs +
  234.                     (pslot - kbot),
  235.                   full = 0;
  236.                }
  237.            }
  238.         else
  239.            {    ref *kbot = pdict->keys.value.refs;
  240.             register ref *kp;
  241.             ref *pslot = 0;
  242.             for ( kp = kbot + (hash % size) + 2; ; )
  243.                {    --kp;
  244.                 if ( (etype = r_type(kp)) == ktype )
  245.                    {    /* Fast comparison if both keys are names */
  246.                     if ( kp->value.pname == kpname )
  247.                        {    *ppvalue = pdict->values.value.refs + (kp - kbot);
  248.                         return 1;
  249.                        }
  250.                    }
  251.                 else if ( etype == t_null )
  252.                    {    /* Empty, deleted, or wraparound. */
  253.                     /* Figure out which. */
  254.                     if ( kp == kbot )    /* wrap */
  255.                        {    if ( wrap++ )    /* wrapped twice */
  256.                            {    if ( full > 0 )
  257.                                {    if ( pslot != 0 )
  258.                                     break;
  259.                                 full = e_dictfull;
  260.                                }
  261.                             goto next_dict;
  262.                            }
  263.                         kp += size + 1;
  264.                        }
  265.                     else if ( r_has_attr(kp, a_executable) )
  266.                        {    /* Deleted entry, save the slot. */
  267.                         if ( pslot == 0 ) pslot = kp;
  268.                        }
  269.                     else    /* key not found */
  270.                         break;
  271.                    }
  272.                 else
  273.                    {    if ( obj_eq(kp, pkey) )
  274.                        {    *ppvalue = pdict->values.value.refs + (kp - kbot);
  275.                         return 1;
  276.                        }
  277.                    }
  278.                }
  279.             if ( full > 0 )
  280.                {    *ppvalue = pdict->values.value.refs +
  281.                   ((pslot != 0 ? pslot : kp) - kbot);
  282.                 full = 0;
  283.                }
  284.            }
  285. next_dict: ;
  286.        }
  287.     while ( --pdref >= pdbot );
  288.     return full;
  289. }
  290.  
  291. /*
  292.  * Look up a name on the dictionary stack.
  293.  * Return the pointer to the value if found, 0 if not.
  294.  * This is just an optimization of dict_lookup with a different interface.
  295.  */
  296. ref *
  297. dict_find_name(ref *pname)
  298. {    ds_ptr pdref = dsp;
  299.     name *kpname = pname->value.pname;
  300.     uint nidx = kpname->index;
  301.     uint hash = dict_name_index_hash(nidx);
  302.     ref_packed kpack = packed_name_key(nidx);
  303.     int wrap = 0;
  304.     do
  305.        {    dict *pdict = pdref->value.pdict;
  306.         uint size = npairs(pdict);
  307.         if ( dict_is_packed(pdict) )
  308.            {    packed_search(0, return, 0);
  309.            }
  310.         else
  311.            {    ref *kbot = pdict->keys.value.refs;
  312.             register ref *kp;
  313.             /* Search the dictionary */
  314.             for ( kp = kbot + (hash % size) + 2; ; )
  315.                {    --kp;
  316.                 if ( r_has_type(kp, t_name) )
  317.                    {    if ( kp->value.pname == kpname )
  318.                       return pdict->values.value.refs +
  319.                         (kp - kbot);
  320.                    }
  321.                 else if ( r_has_type(kp, t_null) )
  322.                    {    /* Empty, deleted, or wraparound. */
  323.                     /* Figure out which. */
  324.                     if ( !r_has_attr(kp, a_executable) )
  325.                         break;
  326.                     if ( kp == kbot )    /* wrap */
  327.                        {    if ( wrap++ )
  328.                             break;    /* 2 wraps */
  329.                         kp += size + 1;
  330.                        }
  331.                    }
  332.                }
  333.            }
  334.        }
  335.     while ( --pdref >= dstack );
  336.     return (ref *)0;
  337. }
  338.  
  339. /*
  340.  * Enter a key-value pair in a dictionary.
  341.  * The caller is responsible for ensuring key is not a null.
  342.  * Return 0, e_dictfull, or e_VMerror if the key was a string
  343.  * and a VMerror occurred when converting it to a name.
  344.  */
  345. int
  346. dict_put(ref *pdref /* t_dictionary */, const ref *pkey, const ref *pvalue)
  347. {    ref *pvslot;
  348.     if ( dict_find(pdref, pkey, &pvslot) <= 0 )    /* not found */
  349.        {    /* Check for overflow */
  350.         dict *pdict = pdref->value.pdict;
  351.         ref kname;
  352.         uint index = pvslot - pdict->values.value.refs;
  353.         if ( pdict->count.value.intval == npairs(pdict) )
  354.             return e_dictfull;
  355.         /* If the key is a string, convert it to a name. */
  356.         if ( r_has_type(pkey, t_string) )
  357.            {    int code = name_from_string(pkey, &kname);
  358.             if ( code < 0 ) return code;
  359.             pkey = &kname;
  360.            }
  361.         if ( dict_is_packed(pdict) )
  362.            {    ref_packed *kp;
  363.             if ( !r_has_type(pkey, t_name) ||
  364.                  name_index(pkey) > packed_max_name_index
  365.                )
  366.                {    /* Change to unpacked representation. */
  367.                 /* We can't just use dict_resize, */
  368.                 /* because the values slots mustn't move. */
  369.                 uint count = nslots(pdict);
  370.                 ref_packed *old_keys = pdict->keys.value.packed;
  371.                 int code;
  372.                 ref *nkp;
  373.                 if ( alloc_save_new_mask )
  374.                     alloc_save_change(&pdict->keys, "dict_unpack(keys)");
  375.                 code = dict_create_unpacked_keys(count, pdict);
  376.                 if ( code < 0 ) return code;
  377.                 for ( kp = old_keys, nkp = pdict->keys.value.refs; count--; kp++, nkp++ )
  378.                   if ( packed_ref_is_name(kp) )
  379.                     packed_get(kp, nkp);
  380.                 alloc_free_refs((ref *)old_keys,
  381.                         (count + packed_per_ref - 1) / packed_per_ref,
  382.                         "dict_unpack(old keys)");
  383.                 return dict_put(pdref, pkey, pvalue);
  384.                }
  385.             kp = pdict->keys.value.packed + index;
  386.             if ( alloc_save_new_mask &&
  387.                  !r_has_attr(&pdict->keys, l_new)
  388.                )
  389.                {    /* See initial comment for why it is safe */
  390.                 /* not to save the change if the keys */
  391.                 /* array itself is new. */
  392.                 alloc_save_change(pdict->keys.value.refs + (index / packed_per_ref), "dict_put(key)");
  393.                }
  394.             *kp = pt_tag(pt_literal_name) + name_index(pkey);
  395.            }
  396.         else
  397.            {    ref *kp = pdict->keys.value.refs + index;
  398.             ref_assign_old(kp, pkey, "dict_put(key)");    /* set key of pair */
  399.            }
  400.         ref_save(&pdict->count, "dict_put(count)");
  401.         pdict->count.value.intval++;
  402.         /* If the key is a name, update its 1-element cache. */
  403.         if ( r_has_type(pkey, t_name) )
  404.            {    name *pname = pkey->value.pname;
  405.             if ( pname->pvalue == pv_no_defn &&
  406.                 (pdict == systemdict.value.pdict ||
  407.                  pdict == userdict.value.pdict) &&
  408.                 /* Only set the cache if we aren't inside */
  409.                 /* a save.  This way, we never have to */
  410.                 /* undo setting the cache. */
  411.                 alloc_save_level() == 0
  412.                )
  413.                {    /* Set the cache */
  414.                 pname->pvalue = pvslot;
  415.                }
  416.             else    /* The cache is worthless */
  417.                 pname->pvalue = pv_other;
  418.            }
  419.        }
  420.     ref_assign_old(pvslot, pvalue, "dict_put(value)");
  421.     return 0;
  422. }
  423.  
  424. /* Remove an element from a dictionary. */
  425. int
  426. dict_undef(ref *pdref, const ref *pkey)
  427. {    ref *pvslot;
  428.     dict *pdict;
  429.     uint index;
  430.     if ( dict_find(pdref, pkey, &pvslot) <= 0 )
  431.         return e_undefined;
  432.     /* Remove the entry from the dictionary. */
  433.     pdict = pdref->value.pdict;
  434.     index = pvslot - pdict->values.value.refs;
  435.     if ( dict_is_packed(pdict) )
  436.        {    ref_packed *pkp = pdict->keys.value.packed + index;
  437.         /* Since packed arrays don't have room for a saved bit, */
  438.         /* always save the entire ref containing this key. */
  439.         /* This wastes a little space, but undef is rare. */
  440.         /* See the initial comment for why it is safe not to save */
  441.         /* the change if the keys array itself is new. */
  442.         if ( alloc_save_new_mask && !r_has_attr(&pdict->keys, l_new) )
  443.             alloc_save_change(pdict->keys.value.refs + (index / packed_per_ref), "dict_undef(key)");
  444.         /* Accumulating deleted entries slows down lookup. */
  445.         /* Detect the easy case where we can use an empty entry */
  446.         /* rather than a deleted one, namely, when the next entry */
  447.         /* in the probe order is empty. */
  448.         if ( pkp[-1] == packed_key_empty )
  449.             *pkp = packed_key_empty;
  450.         else
  451.             *pkp = packed_key_deleted;
  452.        }
  453.     else                /* not packed */
  454.        {    ref *kp = pdict->keys.value.refs + index;
  455.         make_null_old(kp, "dict_undef(key)");
  456.         /* Accumulating deleted entries slows down lookup. */
  457.         /* Detect the easy case where we can use an empty entry */
  458.         /* rather than a deleted one, namely, when the next entry */
  459.         /* in the probe order is empty. */
  460.         if ( !r_has_type(kp - 1, t_null) ||    /* full entry */
  461.              r_has_attr(kp - 1, a_executable)    /* deleted or wraparound */
  462.             )
  463.             r_set_attrs(kp, a_executable);    /* mark as deleted */
  464.        }
  465.     ref_save(&pdict->count, "dict_undef(count)");
  466.     pdict->count.value.intval--;
  467.     /* If the key is a name, update its 1-element cache. */
  468.     if ( r_has_type(pkey, t_name) )
  469.        {    name *pname = pkey->value.pname;
  470.         if ( pv_valid(pname->pvalue) &&
  471.             (pdict == systemdict.value.pdict ||
  472.              pdict == userdict.value.pdict) )
  473.            {    /* Clear the cache */
  474.             pname->pvalue = pv_no_defn;
  475.            }
  476.        }
  477.     make_null_old(pvslot, "dict_undef(value)");
  478.     return 0;
  479. }
  480.  
  481. /* Return the number of elements in a dictionary. */
  482. uint
  483. dict_length(const ref *pdref /* t_dictionary */)
  484. {    return (uint)(pdref->value.pdict->count.value.intval);
  485. }
  486.  
  487. /* Return the capacity of a dictionary. */
  488. uint
  489. dict_maxlength(const ref *pdref /* t_dictionary */)
  490. {    return npairs(pdref->value.pdict);
  491. }
  492.  
  493. /* Copy one dictionary into another. */
  494. int
  495. dict_copy(const ref *pdrfrom /* t_dictionary */, ref *pdrto /* t_dictionary */)
  496. {    int index = dict_first(pdrfrom);
  497.     ref elt[2];
  498.     int code;
  499.     while ( (index = dict_next(pdrfrom, index, elt)) >= 0 )
  500.       if ( (code = dict_put(pdrto, &elt[0], &elt[1])) < 0 )
  501.         return code;
  502.     return 0;
  503. }
  504.  
  505. /* Resize a dictionary. */
  506. int
  507. dict_resize(ref *pdrfrom, uint new_size)
  508. {    dict *pdict = pdrfrom->value.pdict;
  509.     uint count = nslots(pdict);
  510.     dict dnew;
  511.     ref drto;
  512.     int code;
  513.     if ( (code = dict_create_contents(new_size, &dnew, dict_is_packed(pdict))) < 0 ) return code;
  514.     make_tav_new(&drto, t_dictionary, a_all, pdict, &dnew);
  515.     dict_copy(pdrfrom, &drto);    /* can't fail */
  516.     /* Free the old dictionary */
  517.     alloc_free_refs(pdict->values.value.refs, count,
  518.             "dict_resize(old values)");
  519.     alloc_free_refs(pdict->keys.value.refs,
  520.             (dict_is_packed(pdict) ?
  521.              (count + packed_per_ref - 1) / packed_per_ref :
  522.              count),
  523.             "dict_resize(old keys)");
  524.     ref_assign_old(&pdict->keys, &dnew.keys, "dict_resize(keys)");
  525.     ref_assign_old(&pdict->values, &dnew.values, "dict_resize(values)");
  526.     return 0;
  527. }
  528.  
  529. /* Prepare to enumerate a dictionary. */
  530. int
  531. dict_first(const ref *pdref)
  532. {    return (int)nslots(pdref->value.pdict);
  533. }
  534.  
  535. /* Enumerate the next element of a dictionary. */
  536. int
  537. dict_next(const ref *pdref, int index, ref *eltp /* ref eltp[2] */)
  538. {    dict *pdict = pdref->value.pdict;
  539.     ref *vp = pdict->values.value.refs + index;
  540.     while ( vp--, --index >= 0 )
  541.        {    array_get(&pdict->keys, (long)index, eltp);
  542.         /* Make sure this is a valid entry. */
  543.         if ( r_has_type(eltp, t_name) ||
  544.              (!dict_is_packed(pdict) && !r_has_type(eltp, t_null))
  545.            )
  546.            {    eltp[1] = *vp;
  547.             return index;
  548.            }
  549.        }
  550.     return -1;            /* no more elements */
  551. }
  552.